Forbidden graph characterization

A forbidden graph characterization is a method of specifying a family of graph, or hypergraph, structures. Families vary in the nature of what is forbidden. In general, a structure G is a member of a family \mathcal{F} if and only if a forbidden substructure is not contained in G. The forbidden substructure might simply be a subgraph, or a substructure from which one might derive (via, e.g., edge contraction or subdivision) that which is forbidden. Thus, the forbidden structure might be one of:

(Such forbidden structures can also be called obstruction sets.)

Forbidden graph characterizations are utilized in combinatorial algorithms, often for identifying a structure. Such methods can provide a polynomial-time algorithm for determining a graph's membership in a specific family (i.e., a polynomial-time implementation of an indicator function).

A well-known characterization of this kind is the Kuratowski theorem that provides two forbidden homeomorphic subgraphs, using which, one may determine a graph's planarity. Another is the Robertson–Seymour theorem that proves the existence of a forbidden minor characterization for several graph families.

List of forbidden characterizations for graphs and hypergraphs

Family Forbidden graphs Relation Reference
Forests loops, pairs of parallel edges, and cycles of all lengths subgraph Definition
a loop (for multigraphs) or a triangle K3 (for simple graphs) graph minor Definition
Claw-free graphs star K1,3 induced subgraph Definition
Comparability graphs induced subgraph
Triangle-free graphs triangle K3 induced subgraph Definition
Planar graphs K5 and K3,3 homeomorphic subgraph Kuratowski theorem
K5 and K3,3 graph minor Wagner's theorem
Outerplanar graphs K4 and K2,3 graph minor Diestel (2000),[1] p. 107
Graphs of fixed genus a finite obstruction set graph minor Diestel (2000),[1] p. 275
Apex graphs a finite obstruction set graph minor [2]
Linklessly embeddable graphs The Petersen family graph minor [3]
Bipartite graphs odd cycles subgraph [4]
Chordal graphs cycles of length 4 or more induced subgraph [5]
Perfect graphs cycles of odd length 5 or more or their complements induced subgraph [6]
Line graph of graphs nine forbidden subgraphs (listed here) induced subgraph [7]
Graph unions of cactus graphs the four-vertex diamond graph formed by removing an edge from the complete graph K4 graph minor [8]
Ladder graphs K2,3 and its dual graph homeomorphic subgraph [9]
Helly circular-arc graphs induced subgraph [10]
split graphs C_4, C_5, \bar{C_4} (=K_2%2BK_2) induced subgraph [11]
treewidth ≤ 2 (branchwidth ≤ 2) K4 graph minor Diestel (2000),[1] p. 327
treewidth ≤ 3 K5, octahedron, pentagonal prism, Wagner graph graph minor [12]
branchwidth ≤ 3 K5, octahedron, cube, Wagner graph graph minor [13]
Complement-reducible graphs (cographs) 4-vertex path P4 induced subgraph [14]
Trivially perfect graphs 4-vertex path P4 and 4-vertex cycle C4 induced subgraph [15]
Threshold graphs 4-vertex path P4, 4-vertex cycle C4, and complement of C4 induced subgraph [15]
Line graph of 3-uniform linear hypergraphs a finite list of forbidden induced subgraphs with minimum degree at least 19 induced subgraph [16]
Line graph of k-uniform linear hypergraphs, k > 3 a finite list of forbidden induced subgraphs with minimum edge degree at least 2k2 − 3k + 1 induced subgraph [17] [18]
General theorems
a family defined by an induced-hereditary property a (not necessarily finite) obstruction set induced subgraph
a family defined by an minor-hereditary property a finite obstruction set graph minor Robertson–Seymour theorem

See also

References

  1. ^ a b c Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics, 173, Springer-Verlag, ISBN 0387989765 .
  2. ^ Gupta, A.; Impagliazzo, R. (1991), "Computing planar intertwines", Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91), IEEE Computer Society, pp. 802–811, doi:10.1109/SFCS.1991.185452, http://www.cse.ucsd.edu/users/russell/arvind.ps .
  3. ^ Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), "Linkless embeddings of graphs in 3-space", Bulletin of the American Mathematical Society 28 (1): 84–89, arXiv:math/9301216, doi:10.1090/S0273-0979-1993-00335-5, MR1164063 .
  4. ^ Béla Bollobás (1998) "Modern Graph Theory", Springer, ISBN 0387984887 p. 9
  5. ^ Kashiwabara, Toshinobu (1981), "Algorithms for some intersection graphs", in Saito, Nobuji; Nishizeki, Takao, Graph Theory and Algorithms, 17th Symposium of Research Institute of Electric Communication, Tohoku University, Sendai, Japan, October 24-25, 1980, Proceedings, Lecture Notes in Computer Science, 108, Springer-Verlag, pp. 171–181, doi:10.1007/3-540-10704-5\_15 .
  6. ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics 164 (1): 51–229, arXiv:math/0212070v1, doi:10.4007/annals.2006.164.51, http://people.math.gatech.edu/~thomas/PAP/spgc.pdf .
  7. ^ Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J., Beiträge zur Graphentheorie, Leipzig: Teubner, pp. 17–33 .
  8. ^ El-Mallah, Ehab; Colbourn, Charles J. (1988), "The complexity of some edge deletion problems", IEEE Transactions on Circuits and Systems 35 (3): 354–362, doi:10.1109/31.1748 .
  9. ^ Takamizawa, K.; Nishizeki, Takao; Saito, Nobuji (1981), "Combinatorial problems on series-parallel graphs", Discrete Applied Mathematics 3 (1): 75–76, doi:10.1016/0166-218X(81)90031-7 .
  10. ^ Joeris, Benson L.; Lin, Min Chih; McConnell, Ross M.; Spinrad, Jeremy P.; Szwarcfiter, Jayme L. (2009), "Linear-Time Recognition of Helly Circular-Arc Models and Graphs", Algorithmica 59 (2): 215–239, doi:10.1007/s00453-009-9304-5 
  11. ^ Földes, Stéphane; Hammer, Peter L. (1977a), "Split graphs", Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Congressus Numerantium, XIX, Winnipeg: Utilitas Math., pp. 311–315, MR0505860 
  12. ^ Bodlaender, Hans L. (1998), "A partial k-arboretum of graphs with bounded treewidth", Theoretical Computer Science 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4 .
  13. ^ Bodlaender, Hans L.; Thilikos, Dimitrios M. (1999), "Graphs with branchwidth at most three", Journal of Algorithms 32 (2): 167–194, doi:10.1006/jagm.1999.1011 .
  14. ^ Seinsche, D. (1974), "On a property of the class of n-colorable graphs", Journal of Combinatorial Theory, Series B 16 (2): 191–193, doi:10.1016/0095-8956(74)90063-X, MR0337679 
  15. ^ a b Golumbic, Martin Charles (1978), "Trivially perfect graphs", Discrete Mathematics 24 (1): 105–107, doi:10.1016/0012-365X(78)90178-4 ..
  16. ^ Metelsky, Yury; Tyshkevich, Regina (1997), "On line graphs of linear 3-uniform hypergraphs", Journal of Graph Theory 25 (4): 243–251, doi:10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K, MR1459889 
  17. ^ Jacobson, M. S.; Kézdy, Andre E.; Lehel, Jeno (1997), "Recognizing intersection graphs of linear uniform hypergraphs", Graphs and Combinatorics 13: 359–367, MR1485929 
  18. ^ Naik, Ranjan N.; Rao, S. B.; Shrikhande, S. S.; Singhi, N. M. (1982), "Intersection graphs of k-uniform hypergraphs", European J. Combinatorics 3: 159–172, MR0670849